package com.stupidzhe.ds.algorithm;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * @Author: StupidZhe
 * @Date: Created in 2018/3/28
 * @Description: 插入希尔排序
 */
public class ShellSort {

    // 步长
    private static final int step = 12;

    public static List<Integer> sort(List<Integer> content) {

        int size = content.size();

        // 步长依次减小
        for (int n = step; n > 0; n--) {
            for (int nn = 0; nn < n; nn++) {
                for (int m = n + nn; m < size; m += n) {
                    Integer tmp;
                    for (int t = m - n; t > -1 && (tmp = content.get(t)) > (content.get(t + n)); t -= n) {
                        content.set(t, content.get(t + n));
                        content.set(t + n, tmp);
                    }
                }
            }
        }
        return content;
    }

    @Test
    public void test1() {
        List<Integer> content = new LinkedList<>();
        Random random = new Random(12312);
        for (int n = 0; n < 5000; n++)
            content.add(random.nextInt(100000));
        long start = System.currentTimeMillis();
        sort(content);
        System.out.println(System.currentTimeMillis() - start);
    }
}
